package Algorithm;
import java.util.*;


class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}
public class Work4 {
    /*二叉树相关题型*/
        /*/经典二叉树问题
    //解题思路：
    //根据root节点，将中序vector划分成vin_left，vin_right两部分中序子序列
    //根据中序子序列长度，将前序vector划分成pre_left, pre_right对应的前序子序列
    //root->left递归生成
    //root->right递归生成*/

    public int preIndex = 0;
    public TreeNode createTreeByPandI(int[] preorder, int[] inorder,int inbegin,int inend) {

        if(inbegin > inend) {
            //如果满足这个条件  说明 没有左树 或者 右树了
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //找到根在中序遍历的位置
        int rootIndex = findIndexOfI(inorder,inbegin,inend,preorder[preIndex]);
        if(rootIndex == -1) {
            return null;
        }
        preIndex++;
        //分别创建 左子树 和 右子树
        root.left = createTreeByPandI(preorder,inorder,inbegin,rootIndex-1);
        root.right = createTreeByPandI(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    private int findIndexOfI(int[] inorder,int inbegin,int inend,int key) {

        for(int i = inbegin; i <= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre == null ||  vin == null) return null;

        return createTreeByPandI(pre, vin,0,vin.length-1);
    }
    /*判断一颗树,是不是另一颗树的子结构
    * 解题思路:递归*/
    private boolean IsSame(TreeNode root1,TreeNode root2){
        /*比较左右子树是否相等*/
        if (root2 == null){
            return true;
        }
        if (root1 == null){
            return false;
        }
        if (root1.val != root2.val){
            return false;
        }
        return IsSame(root1.left,root2.left)&&IsSame(root1.right,root2.right);
    }
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root2 == null || root1 == null){
            return false;
        }
        boolean result=false;
        if (root1.val == root2.val){
            result = IsSame(root1,root2);
        }
        if (result != true){
           result = HasSubtree(root1.left,root2);
        }
        if (result != true){
           result = HasSubtree(root1.right,root2);
        }
        return result;
    }
    /*镜像二叉树：将二叉树变成镜像二叉树*/
    public TreeNode Mirror (TreeNode root) {
        // write code here
        if (root == null){
            return null;
        }
        TreeNode newLeft= Mirror(root.right);;
        TreeNode newRight=Mirror(root.left);;
        root.left=newLeft;
        root.right=newRight;
        return root;
    }
    /*二叉搜索树的后序遍历序列
    * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
    * 如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
    * 解题思路:分治思想,
    * //BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是root节点），如果去掉最后一个元素的序列为
    T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列
    //验证思路就是：当前序列，及其子序列必须都满足上述定义*/
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        return VerifySquenceOfBST_Fun(sequence,0,sequence.length-1);

    }
    private  boolean VerifySquenceOfBST_Fun(int[] sequence,int start ,int end){
        /*结束条件*/
        if (start >= end){
            return true;
        }
        int root = sequence[end];
        int i=start;
        while (i < end && sequence[i] < root){
            i++;
        }
        for (int j = i; j < end; j++) {
            if (sequence[j] < root){
                return false;
            }
        }
        //走到这里，就说明，当前序列满足需求。但并不代表题目被解决了，还要在检测left和right各自是否也满足
        return VerifySquenceOfBST_Fun(sequence,start,i-1)
                &&VerifySquenceOfBST_Fun(sequence,i,end-1);
    }






    /*二叉树中和为某一值的路径(二)
    输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
    1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
    2.叶子节点是指没有子节点的节点
    3.路径只能从父节点到子节点，不能从子节点到父节点
    4.总节点数目为n*/
    /*回溯法:大概率有一层结果集(ArrayList<ArrayList<Integer>>)与一层待选结果集(ArrayList<Integer>)
    * 回溯法的本质:基于二叉树,多叉树的穷举-剪枝
    * 1:先添加值
    * 2:判定现有结果是否满足条件
    * 3:深度优先
    * 4:回退*/
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<ArrayList<Integer>> arrayList=new ArrayList<>();
        ArrayList<Integer> list=new ArrayList<>();
        FindPath_Func(root,expectNumber,arrayList,list);
        return arrayList;
    }
    private void FindPath_Func(TreeNode root,int expectNumber,
                               ArrayList<ArrayList<Integer>> arrayList,ArrayList<Integer> list){
        if (root == null){
            return;
        }
        list.add(root.val);
        expectNumber -= root.val;
        //1. 已经是叶子节点了
        //2. 从root到该叶子节点，之和是target
        //3. 是叶子节点，但是不满足节点，也不影响，程序会直接退出
        if (root.left == null && root.right == null && expectNumber == 0){
            /*这儿为什么需要深浅拷贝,为什么直接add(list)是错误的?
            * 浅拷贝只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存（分支）
            * 深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象，是“值”而不是“引用”（不是分支）
            * 这就是为什么这儿用深拷贝,因为如果是浅拷贝的话,你最后减枝,减的原有对象都为空了,输出结果也就都是空了*/
            arrayList.add(new ArrayList<Integer>(list));
        }
        FindPath_Func(root.left,expectNumber,arrayList,list);//DFS递归统计
        FindPath_Func(root.right,expectNumber,arrayList,list);
        int k=list.size()-1;
        list.remove(k);
    }

}
